/*Source

Problem Id:2696  User Id:Latex 
Memory:72K  Time:0MS
Language:G++  Result:Accepted

Source 
*/
#include <cstdio>
#include <cstring>

	int Ncase;
	int ct;
	int a, b, c, d, e, f, g, h,m;
	int phi[2000];

main()
{
	int t;
	int i;
	
	//freopen("c.in", "r", stdin);
	
	scanf("%ld", &Ncase);
	for (ct=1; ct<=Ncase; ct++)
	{
		scanf("%ld%ld%ld%ld%ld%ld%ld%ld%ld", &a, &b ,&c, &d, &e, &f, &g, &h, &m) ;
		phi[0] = a;
		phi[1] = b;
		phi[2] = c;
		for (i=3; i<=m; i++)
		{
			if (i & 1) //odd
			{
				t = d * phi[i-1] + e * phi[i-2] - f * phi[i-3];
				while (t < 0)
					t += g;
				phi[i] = t % g;
			} else
			{
				t = f * phi[i-1] - d * phi[i-2] + e * phi[i-3];
				while (t < 0)
					t += h;
				phi[i] = t % h;
			}
		}
		printf("%ld\n", phi[m]);
	}
	return 0;
}

